<?php
/**
 * <https://y.st./>
 * Copyright © 2018 Alex Yst <mailto:copyright@y.st>
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <https://www.gnu.org./licenses/>.
**/

$xhtml = array(
	'<{title}>' => 'More colours?',
	'takedown' => '2017-11-01',
	'<{body}>' => <<<END
<img src="/img/CC_BY-SA_4.0/y.st./weblog/2018/12/20.jpg" alt="The complex across the way" class="framed-centred-image" width="649" height="480"/>
<section id="dreams">
	<h2>Dream journal</h2>
	<p>
		I dreamed I got swept under the ocean, and when I resurfaced, I was in some sort of cave.
		The only exit was underwater, in the pool I&apos;d surfaced from.
		Three other people had been with me and had washed into the cave too.
		There was a doorway-like hole in the wall, which lead to another cave chamber.
		I entered that chamber alone, and found that someone had probably once lived in there.
		There were a couple old couches covered in junk.
		I started picking though the junk, collecting whatever coins I could.
		About half the currency was foreign, but I took that too.
		I found a credit card, but left that were it was.
		I woke up before I could collect all the coins.
	</p>
	<p>
		Except I wasn&apos;t really awake.
		In this part of the dream, I was going to organise my bedroom.
		For some reason, I was considering moving spice racks into my bedroom, but thought there wasn&apos;t really space for them there.
		I was disappointed about not getting to keep the coins I&apos;d collected, knowing that last part hadn&apos;t been real.
	</p>
	<p>
		Once I actually woke up in the real world though, I didn&apos;t care about the cave couch coins.
	</p>
</section>
<section id="health">
	<h2>Health</h2>
	<p>
		I finally got to bed before midnight last night for the first time in probably over a month.
		Yet somehow, I woke up very tired.
		After getting most of the reading done I needed to get the discussion post in for the day, I ended up taking a nap before continuing.
		I didn&apos;t get as much done as I&apos;d really like to have, however, I&apos;m finally not behind any more.
		This is the first week in a while where I&apos;m starting out where I should.
		So I guess I wouldn&apos;t say I&apos;m behind yet.
	</p>
	<p>
		I&apos;ve also gone back to shaving.
		I kind of quit so I could try that hair-removal remedy, and that didn&apos;t work out.
		I&apos;d forgotten how good it feels to have smooth, hairless skin.
	</p>
</section>
<section id="drudgery">
	<h2>Drudgery</h2>
	<p>
		My discussion post for the day:
	</p>
	<blockquote>
		<p>
			Quicksort chooses a pivot point, and shuffles all values less than it to the beginning of the array, and all values less than or equal to it to the end of the array.
			It then recursively calls itself on two sub-arrays, separated by the point where the pivot value fell, which is between the two sets of values.
		</p>
		<p>
			Choosing a good pivot point is incredibly important, as it determines the efficiency of the recursive calls.
			If a bad pivot point is chosen, all other values may get shuffled to the same side of it.
			This causes the divide-and-conquer approach to fail.
			Instead of a single value being removed and the rest divided between two recursive calls, a single values is removed and the problem otherwise doesn&apos;t get divided at all before getting passed on to the recursive call.
		</p>
		<p>
			The discussion question asks how a pivot point is chosen.
			That entirely depends on the implementation.
			There is no one way to choose a pivot point.
			However, you have to weigh the cost of choosing a pivot point with the cost of failing to choose a good pivot point.
			For example, one way to choose a pivot point would be at complete random.
			However, random number generator calls are expensive (Shaffer, 2011).
			Therefore, it&apos;d make quick sort inefficient to do that.
			Another option is to choose the central value of the current sub array.
			It&apos;s unlikely that the value physically located directly in the middle will be on either end of the sorted sub-array, so it&apos;ll probably work out fine (Shaffer, 2011).
			Much efficiency is gained here by not calling the random number generator, but both with this method and the random number generator method, it&apos;s still <strong>*possible*</strong> to choose a bad pivot point, and that would cause a drop in efficiency.
			Another option is to choose three prospective pivot points, such as the first value in the sub-array, the last value, and the middle value (Shaffer, 2011).
			Whichever of these values is neither the maximum nor minimum of the three can be used as the pivot point.
			This almost eliminates the chances of a bad pivot being chosen.
			The only way a bad pivot would be chose is if two or all three of these values were equal.
			However, this method also adds more overhead to the problem.
			Does the extra cost in choosing a pivot outweigh the reduced chances of choosing a bad pivot?
		</p>
		<p>
			It&apos;s also possible to create a sort of hybrid sorting method using quick sort.
			Quick sort can separate things into smaller, mostly-sorted groups, and pass the work off to insertion sort to finish the job (Shaffer, 2011).
		</p>
		<div class="APA_references">
			<h3>References:</h3>
			<p>
				Shaffer, C. (2011). A Practical Introduction to Data Structures and Algorithm Analysis. Retrieved from <a href="https://my.uopeople.edu/pluginfile.php/356474/mod_page/content/2/Practical_Into_to_Data_Structures_and_Algorithms_-_Shaffer.pdf"><code>https://my.uopeople.edu/pluginfile.php/356474/mod_page/content/2/Practical_Into_to_Data_Structures_and_Algorithms_-_Shaffer.pdf</code></a>
			</p>
		</div>
	</blockquote>
</section>
<section id="Minetest">
	<h2>Minetest</h2>
	<p>
		Since the advent of paletted nodes in Minetest, I&apos;ve been trying to squeeze as many node colours into the palette as possible.
		On a regular paletted node, you get 256 colours.
		That&apos;s it, plain and simple.
		Colour is assigned based on the <code>param2</code> value of the node, and <code>param2</code> is an 8-bit integer.
		However, there are also wall-mounted coloured nodes and direction-facing coloured nodes.
		In these nodes, <code>param2</code> not only represents the colour of the node, but also the direction the node is facing or mounted.
		That leaves less space for colour data, so you get less colours.
	</p>
	<p>
		Previously, I tried using coloured wall-mounted nodes to construct a bed system.
		Beds can only be faced four directions, not all twenty-four directions, so it didn&apos;t make sense to me to use the direction-facing node type, as it eats up way too many bits.
		I&apos;d get four times as many colours if I hacked in functionality to make the coloured wall-mounted node type work instead.
		However, it wasn&apos;t meant to be.
		Wall-mounted nodes, for whatever reason, rotate their node boxes, but <strong>*not*</strong> their textures.
		In retrospect, I&apos;m pretty sure the textures <strong>*do*</strong> get rotated if you use meshes instead of node boxes, but I can&apos;t find any information on how to construct a Minetest mesh, so that&apos;s not really an option.
		I figured I just couldn&apos;t squeeze any extra colours in like I wanted to.
	</p>
	<p>
		I decided to run a calculation today though.
		For simplicity, the rendering in Minetest actually uses the unmodified <code>param2</code> value for <strong>*both*</strong> it&apos;s functions.
		So, the rotation becomes some excessively-high number and the colour values are repeated for many colour values in a row, and that makes it look like you&apos;ve gotten two separate values into the 8-bit <code>param2</code> value.
		But what if the rendering was done in a more-complex way, and therefore didn&apos;t need the split to be along a bit line?
		I ran a calculation and found that the coloured direction-facing node type could allow ten different colours instead of the current eight.
		Could I tap into even a little of that potential by exploiting the way Minetest uses the value?
	</p>
	<p>
		It turns out that I can, with rather decent results.
		There&apos;s some odd wrapping done in the direction-facing number.
		First, the number gets looked at modulo 32.
		That allows the low-order five bits to deal with rotation, wile the upper three bits deal with colour.
		However, there are only 24 rotations, so the number goes through modulo division a <strong>*second*</strong> time, this time by 24.
		This results in a weird repeating of eight facing directions.
		I say it&apos;s weird, but at the same time, I actually predicted that would happen; I tested for that behaviour specifically because I thought it highly probable.
		So now, we have eight facing directions that appear twice as often as the other sixteen.
		Four of those facings are exactly the ones most likely to be useful, and exactly the four needed for beds.
		Chests, if restricted to not lying on their sides or upside-down also make use of these directions.
		The other four duplicated directions involve tipping the chest&apos;s axis to an arbitrary direction, then changing the facing around that axis.
		Not overly useful.
	</p>
	<p>
		Okay, so let&apos;s put this all together now.
		As I said, the value doesn&apos;t actually get split when dealing with colour-rendering.
		Instead, thirty-two pallet indexes in a row just map to the same colour.
		But what if they <strong>*don&apos;t*</strong> map to the same colour?
		And what if custom drop code is set up to assign the correct pallet index to the node&apos;s dropped item?
		And what if the node is restricted to only appearing in one of the four common directions?
		In this case, we don&apos;t get the ten colours we&apos;d be able to fully support with some engine modifications.
		Instead, we get a whopping <strong>*sixteen*</strong> colours.
		The catch is that the node can&apos;t be tipped upside-down or to the side.
		And sometimes, that&apos;s alright.
	</p>
	<p>
		I tried a thought experiment with the wall-mounted colour nodes, but only two rotation values would be repeated, even if the concept from direction-facing nodes does in fact also apply to wall-mounted nodes.
		I don&apos;t see restricting wall-mounted nodes to only mounting on walls in two directions as being useful, so I didn&apos;t actually run any code experiments to test this.
	</p>
	<p>
		For beds and other non-cubic nodes, I&apos;m still convinced wall-mounted coloured nodes are the answer.
		I just need to figure out ow to use meshes.
		However, for cubic things, such as chests, which don&apos;t make sense to place sideways or upside-down, this hack provides great results.
		I just need to figure out what sixteen colours should be supported.
	</p>
</section>
END
);
